Largest number from list of integers

Time: O(NLogN); Space: O(1); medium

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: nums = [10, 2]

Output: “210”

Example 2:

Input: nums = [3, 30, 34, 5, 9]

Output: “9534330”

Note:

  • The result may be very large, so you need to return a string instead of an integer.

1. Sorting via Custom Comparator

Intuition

To construct the largest number, we want to ensure that the most significant digits are occupied by the largest digits.

Algorithm

First, we convert each integer to a string. Then, we sort the array of strings.

While it might be tempting to simply sort the numbers in descending order, this causes problems for sets of numbers with the same leading digit. For example, sorting the problem example in descending order would produce the number 95343039534303, while the correct answer can be achieved by transposing the 3 and the 30. Therefore, for each pairwise comparison during the sort, we compare the numbers achieved by concatenating the pair in both orders. We can prove that this sorts into the proper order as follows:

Assume that (without loss of generality), for some pair of integers a and b, our comparator dictates that aa should precede b in sorted order. This means that a⌢b > b⌢a (where ⌢ represents concatenation).

For the sort to produce an incorrect ordering, there must be some c for which bb precedes c and c precedes a.

This is a contradiction because a⌢b > b⌢a and b⌢c > c⌢b implies a⌢c > c⌢a.

In other words, our custom comparator preserves transitivity, so the sort is correct.

Once the array is sorted, the most “signficant” number will be at the front.

There is a minor edge case that comes up when the array consists of only zeroes, so if the most significant number is 00, we can simply return 00. Otherwise, we build a string out of the sorted array and return it.

[1]:

class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x

class Solution1(object):
    """
    Time: O(NlgN). Although we are doing extra work in our comparator, it is only by a constant factor.
          Therefore, the overall runtime is dominated by the complexity of sort, which is O(NLgN).
    Space: O(n). Here, we allocate O(n) additional space to store the copy of nums.
           Although we could do that work in place (if we decide that it is okay to modify nums),
           we must allocate O(n) space for the final return string.
           Therefore, the overall memory footprint is linear in the length of nums.
    """
    def largestNumber(self, nums) -> str:
        '''
        :type nums: List[int]
        :rtype: str
        '''
        largest_num = ''.join(sorted(map(str, nums), key = LargerNumKey))

        return '0' if largest_num[0] == '0' else largest_num

[2]:

s = Solution1()
nums = [10, 2]
assert s.largestNumber(nums) == "210"
nums = [3, 30, 34, 5, 9]
assert s.largestNumber(nums) == "9534330"

[3]:

class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x

class Solution2(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if len(nums) == 0:
            return ""

        numsStr = [str(n) for n in nums]
        numsStr.sort(key = LargerNumKey)

        if numsStr[0] == '0':
            return "0"
        else:
            return "".join(numsStr)

[4]:

s = Solution2()
nums = [10, 2]
assert s.largestNumber(nums) == "210"
nums = [3, 30, 34, 5, 9]
assert s.largestNumber(nums) == "9534330"